package graph

import (
	"math"
)

func DijKstra(from *Node) map[*Node]int {
	nodeSet := map[*Node]bool{}
	distanceMap := map[*Node]int{}
	distanceMap[from] = 0
	nodeWithDis := GetMinDistanceWithoutSelected(distanceMap, nodeSet)
	for nodeWithDis != nil {
		distanceMap[nodeWithDis.Node] = nodeWithDis.Distances
		for _, edge := range nodeWithDis.Node.OutEdges {
			if nodeSet[edge.To] {
				distanceMap[edge.To] = min(distanceMap[edge.To], edge.Weight+nodeWithDis.Distances)
			} else {
				distanceMap[edge.To] = edge.Weight+nodeWithDis.Distances
			}
		}
		nodeSet[nodeWithDis.Node] = true
		nodeWithDis = GetMinDistanceWithoutSelected(distanceMap, nodeSet)
	}
	return distanceMap
}

func min(a, b int) int {
	if a > b {
		return b
	}
	return a
}

type NodeWithDistance struct {
	Node     *Node
	Distances int
}

func GetMinDistanceWithoutSelected(distanceMap map[*Node]int, nodeSet map[*Node]bool) *NodeWithDistance {
	var ans *NodeWithDistance
	minDistanc := math.MaxInt64
	for node, distance := range distanceMap {
		if !nodeSet[node] {
			if distance < minDistanc {
				minDistanc= distance
				ans = &NodeWithDistance{Node: node, Distances: distance}
			}
		}
	}
	return ans
}